package com.binarysearch;

public class Solution528 {
    int[] sum;

    public Solution528(int[] w) {
        int m = w.length;
        sum = new int[m];
        sum[0] = w[0];
        for (int i = 1; i < m; i++) {
            sum[i] = sum[i - 1] + w[i];
        }
    }

    public int pickIndex() {
        int n = sum.length;
        int x = (int) (Math.random() * sum[n - 1]) + 1;
        int i = 0;
        int j = n - 1;
        while (i < j) {
            int mid = i + j >> 1;
            if (sum[mid] < x) i = mid + 1;
            else j = mid;
        }
        return i;
    }
}
